#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int longest_mismatch(string&s1, string& s2, size_t  i, size_t  j, size_t  K)
{
    size_t size1 = s1.size();
    size_t size2 = s2.size();
    size_t diff_count = 0;
    size_t step_count = 0;
    while(i < size1 && j < size2 && diff_count < K)
    {
        if(s1[i] != s2[j])
            diff_count = diff_count + 1;
        step_count = step_count + 1;
        i = i + 1;
        j = j + 1;
    }
    while(i < size1 && j < size2)
    {
        if(s1[i] == s2[j])
            step_count = step_count + 1;
        else
            break;
        i = i + 1;
        j = j + 1;
    }
    return step_count;
}

int main()
{
    int nStrs = 0;
    cin >> nStrs;
    // cout << "nStrs: " << nStrs << endl;
    while (nStrs-- > 0)
    {
        size_t K;
        string s1, s2;
        cin >> K;
        cin >> s1;
        cin >> s2;
        // cout << "K: " << K << " s1: " << s1 << " s2: "<< s2 << endl;
        size_t size1 = s1.size();
        size_t size2 = s2.size();
        int** L_table = new int*[size1];
        for(size_t  i = 0; i < size1; i++)
        {
            L_table[i] = new int[size2];
        }
        for(size_t  i = 0; i < size1; i++)
        {
            for(size_t  j = 0; j < size2; j++)
            {
                L_table[i][j] = 0;
            }
        }

       for(size_t  i = 0; i < size1; i++)
       {
           int x = longest_mismatch(s1, s2, i, 0, K);
           L_table[i][0] = x;
       }

        for(size_t  i = 0; i < size2; i++)
        {
            L_table[0][i] = longest_mismatch(s1, s2, 0, i, K);
        }

        for(size_t  i = 1; i < size1; i++)
        {
            for(size_t  j = 1; j < size2; j++)
            {
                size_t previous_count = L_table[i - 1][j - 1];
                if(s1[i-1] == s2[j-1])
                    L_table[i][j] = previous_count - 1;
                else
                {
                    size_t shift_count = 0;
                    size_t posi = i + previous_count;
                    size_t posj = j + previous_count;
                    while(posi < size1 && posj < size2)
                    {
                        shift_count = shift_count + 1;
                        if(s1[posi] != s2[posj]) break;
                        posi = posi + 1;
                        posj = posj + 1;
                    }
                    L_table[i][j] = previous_count - 1 + shift_count;
                }
            }
        }
        size_t max_L = 0;
        for(size_t  i = 0; i < size1; i++)
        {
            for(size_t  j = 0; j < size2; j++)
            {
                if(L_table[i][j] > max_L)
                    max_L = L_table[i][j];
            }
        }
        for(size_t  i = 0; i < size1; i++)
        {
            delete[] L_table[i];
        }
        cout << max_L << endl;
    }
}

